package main

type ListNode struct {
	Val  int
	Next *ListNode
}

// 哈希表来做
func detectCycle1(head *ListNode) *ListNode {
	// 定义一个头节点
	cur := &ListNode{0, head}
	// 定义一个hash表存储 key=*ListNode  value=l->next
	mp := make(map[*ListNode]*ListNode)
	temp := cur
	for ; temp != nil; temp = temp.Next {
		if mp[temp.Next] != nil {
			return temp.Next
		}
		mp[temp] = temp.Next
	}
	return nil
}

// 快慢指针
func detectCycle(head *ListNode) *ListNode {
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			newhead := head
			for {
				if newhead == slow {
					return slow
				} else {
					newhead = newhead.Next
					slow = slow.Next
				}
			}
		}

	}
	return nil

}
func main() {
	v1 := &ListNode{3, nil}
	v2 := &ListNode{2, nil}
	v3 := &ListNode{0, nil}
	v4 := &ListNode{4, nil}
	v1.Next = v2
	v2.Next = v3
	v3.Next = v4
	v4.Next = v2
	detectCycle1(v1)
	detectCycle(v1)
}
